class Solution {
public:
    vector<int> father;
    int count;
    
    int find(int u){
        return father[u] == u ? u : find(father[u]);
    }
    
    void Union(int x,int y){
        int u = find(x);
        int v = find(y);
        if(u == v){
            return;
        }
        
        father[v] = u;
        count--;
    }
    
    int minSwapsCouples(vector<int>& row) {
        int n = row.size();
        count = n / 2;
        father.resize(n / 2);
        for(int i = 0;i < n / 2;i++){
            father[i] = i;
        }
        
        for(int i = 1;i < n;i += 2){
            Union(row[i-1]/2,row[i]/2);
        }
        
        return n / 2 - count;
    }
};
